package JZOffer;

import java.util.*;

public class _丑数_ {
    public static void main(String[] args) {
        _丑数_ c = new _丑数_();
        _丑数_.Solution s = c.getSolution();
        Scanner sc = new Scanner(System.in);
        int index = 0;
        while (sc.hasNext()){
            System.out.println(s.GetUglyNumber_Solution(sc.nextInt()));
        }
    }

    Solution getSolution()  {
        return new Solution();
    }

    class Solution {
        public int GetUglyNumber_Solution(int index) {
            if(index<=0)
                return 0;
            ArrayList<Integer> list = new ArrayList<Integer>();
            //add进第一个丑数1
            list.add(1);
            //三个下标用于记录丑数的位置
            int i2=0,i3=0,i5=0;
            while(list.size()<index){
                //三个数都是可能的丑数，取最小的放进丑数数组里面
                int n2=list.get(i2)*2;
                int n3=list.get(i3)*3;
                int n5=list.get(i5)*5;
                int min = Math.min(n2,Math.min(n3,n5));
                list.add(min);
                if(min==n2)
                    i2++;
                if(min==n3)
                    i3++;
                if(min==n5)
                    i5++;
            }
            return list.get(list.size()-1);
        }
    }

    /*class Solution {
        public int GetUglyNumber_Solution(int index) {
            Set res = new HashSet();
            Set now = new HashSet();
            int[] YZ = {2,3,5};
            now.add(1);
            now.add(2);
            now.add(3);
            now.add(5);
//            Iterator it = now.iterator();
//            while (it.hasNext()){
//                System.out.println(it.next());
//            }
            for (int i = 0; i < index; i++) {
                Set newSet = new HashSet();
                for (int j = 0; j < YZ.length; j++) {
                    Iterator it = now.iterator();

                    while (it.hasNext()){
                        int latest =Integer.valueOf(it.next().toString())*YZ[j];
                        if(latest > 0) newSet.add(latest);
                    }
                }
                now.addAll(newSet);
//                if (now.size()>index)
//                    break;
            }

            Set<Integer> sortSet = new TreeSet<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1.compareTo(o2);
                }
            });

            sortSet.addAll(now);
            Iterator it = sortSet.iterator();
            while (it.hasNext()) {
//                System.out.println(it.next());
                if (--index == 0)
                    return (int)it.next();
                it.next();
            }
            return 0;
        }
    }*/
}
